\subsection{Definition}
For sets \(A\) and \(B\), a function \(f\) from \(A\) to \(B\) is a rule that assigns to each \(x \in A\) a unique value \(f(x) \in B\).
More precisely, a function from \(A\) to \(B\) is a set \(f \subseteq A \times B\) such that for every \(x \in A\), there is a unique \(y \in B\) with \((x, y) \in f\).
Of course therefore, if \((x, y) \in f\) then we can write \(f(x) = y\).
Here are some examples.
\begin{enumerate}
	\item \(f\colon \mathbb R \to \mathbb R\) given by \(f(x) = x^2\), or using an alternative notation, \(x \mapsto x^2\) is a function.
	\item A non-example is \(f\colon \mathbb R \to \mathbb R\) given by \(f(x) = \frac{1}{x}\) since it is undefined at \(x=0\).
	\item Another non-example is \(f\colon \mathbb R \to \mathbb R\) given by \(f(x) = \pm \sqrt{\abs{x}}\) since it does not define a unique value in the output space for a given input, such as \(x=2\).
	\item \(f\colon \mathbb R \to \mathbb R\) given by
	      \[
		      f(x) = \begin{cases}
			      1 & x \in \mathbb Q  \\
			      0 & \text{otherwise}
		      \end{cases}
	      \]
	      is a function since it clearly satisfies the second definition.
	      Note that even though we don't know if \(e + \pi\) is rational or not, the function is still well defined since it produces a unique solution for \(f(e + \pi)\), we just don't know which output value it gives.
	\item \(A = \{ 1, 2, 3, 4, 5 \}\), \(B = \{ 1, 2, 3, 4 \}\), and \(f\colon A \to B\) is given by
	      \begin{align*}
		      f(1) & = 1 \\
		      f(2) & = 4 \\
		      f(3) & = 3 \\
		      f(4) & = 3 \\
		      f(5) & = 4
	      \end{align*}
	\item \(A = \{ 1, 2, 3 \}\), \(f\colon A \to A\) is given by
	      \begin{align*}
		      f(1) & = 1 \\
		      f(2) & = 3 \\
		      f(3) & = 2
	      \end{align*}
	\item \(A = \{ 1, 2, 3, 4 \}\), \(f\colon A \to A\) is given by
	      \begin{align*}
		      f(1) & = 1 \\
		      f(2) & = 3 \\
		      f(3) & = 3 \\
		      f(4) & = 4
	      \end{align*}
	\item \(A = \{ 1, 2, 3, 4 \}\), \(B = \{ 1, 2, 3 \}\), \(f\colon A \to B\) is given by
	      \begin{align*}
		      f(1) & = 3 \\
		      f(2) & = 3 \\
		      f(3) & = 2 \\
		      f(4) & = 1
	      \end{align*}
\end{enumerate}

\subsection{Injection, surjection and bijection}
\begin{definition}
	A function \(f\colon A \to B\) is
	\begin{itemize}
		\item injective, if \(\forall a, a' \in A\), we have \(a \neq a' \implies f(a) \neq f(a')\), or equivalently, \(f(a) = f(a') \implies a = a'\), or in words, `different points stay different' (e.g.
		      example 6 above).
		\item surjective, if \(\forall b \in B\), \(\exists a \in A\) such that \(f(a) = b\), or in words, `everything in \(B\) is hit' (e.g.
		      examples 6 and 8).
		\item bijective, if it is injective and surjective, or in words, `everything in \(B\) is hit exactly once', or `\(f\) pairs up elements of \(A\) and elements of \(B\)' (e.g.
		      example 6, or \(f\colon \mathbb R \to \mathbb R\) given by \(f(x) = x^3\)).
	\end{itemize}
\end{definition}
\begin{definition}
	For a function \(f\colon A \to B\), \(A\) is the domain, \(B\) is the range, and \(\{ b \in B : \exists a \in A \st f(a) = b \}\) is the image.
\end{definition}
We must always provide the domain and range of a function; a function's properties depend on this.
For example, is the function \(f\) defined by \(f(x) = f^2\) injective?
If \(f\colon \mathbb N \to \mathbb N\), then it is injective, but if \(f\colon \mathbb Z \to \mathbb Z\), then it is not.

There are a number of properties that hold specifically for finite sets \(A\), \(B\):
\begin{enumerate}
	\item There is no surjection \(A \to B\) if \(\abs{B} > \abs{A}\).
	\item There is no injection \(A \to B\) if \(\abs{A} > \abs{B}\).
	\item For a function \(f\colon A \to A\), \(f\) injective \(\iff\) \(f\) surjective.
	      Hence, if \(f\) is either injective or surjective, it is bijective.
	\item There is no bijection from \(A\) to any proper subset of \(A\).
\end{enumerate}
As counterexamples for infinite sets:
\begin{enumerate}
	\item We define \(f_0\colon \mathbb N \to \mathbb N\) by \(f_0(x) = x+1\).
	      Then, \(f_0\) is injective but not surjective.
	\item We define \(f_1\colon \mathbb N \to \mathbb N\) by \(f_0(x) = x-1\), or 1 if \(x=1\).
	      Then, \(f_0\) is surjective but not injective.
	\item We define \(g\colon \mathbb N \to \mathbb N \setminus \{ 1 \}\) by \(g(x) = x+1\).
	      Then, \(g\) is bijective between \(\mathbb N\) and a proper subset of \(\mathbb N\).
\end{enumerate}
We provide some more examples of functions.
\begin{enumerate}
	\item For any set \(X\) we have \(1_X\colon X \to X\) defined by \(1_X(x) = x\).
	      This is known as the identity function on \(X\).
	\item For any set \(X\), and \(A \subset X\), we have an indicator function (or characteristic function) \(\chi_A\colon X \to \{ 0, 1 \}\) defined by
	      \[
		      \chi_A(x) = \begin{cases}
			      0 & x \notin A \\
			      1 & x \in A
		      \end{cases}
	      \]
	\item A sequence of reals \(x_1, x_2, \dots\) is a function \(f\colon \mathbb N \to \mathbb R\) defined by \(f(n) = x_n\).
	\item The operation \(+\) on \(\mathbb N\) is a function \(\mathbb N^2 \to \mathbb N\).
	\item A set \(X\) has size \(n\) \(\iff\) there is a bijection between \(X\) and \(\{ 1, 2, \dots, n \}\).
\end{enumerate}

\subsection{Composition of functions}
Given \(f\colon A \to B\) and \(g\colon B \to C\), we define the composition \(g\circ f \colon A \to C\), given by \((g\circ f)(a) = g(f(a))\).
For example, if \(f\colon \mathbb R \to \mathbb R\), \(f(x) = 2x\), \(g\colon \mathbb R \to \mathbb R\), \(g(x) = x+1\), then \((f \circ g)(x) = 2(x+1)\), and \((g \circ f)(x) = 2x + 1\).

In general, the operation \(\circ\) is not commutative, as we can see from this example.
However, \(\circ\) is associative.
Given \(f\colon A \to B\), \(g\colon B \to C\), \(h\colon C \to D\), we have \(h \circ (g \circ f) = (h \circ g) \circ f\).
Indeed, for any input \(x \in A\),
\[
	(h \circ (g \circ f))(x) = h((g \circ f)(x)) = h(g(f(x))) = (h \circ g)(f(x)) = ((h \circ g)\circ f)(x)
\]
Thus \((h \circ (g \circ f))(x) = ((h \circ g)\circ f)(x)\) for every \(x \in A\), so \(h \circ (g \circ f) = (h \circ g)\circ f\).

\subsection{Invertibility}
We say that a function \(f\colon A \to B\) is invertible if there exists some \(g\colon B \to A\) such that \(g \circ f = 1_A\) and \(f \circ g = 1_B\).
For example \(f\colon \mathbb R \to \mathbb R\) given by \(f(x)=2x+1\) has inverse \(g\colon \mathbb R \to \mathbb R\) given by \(g(x)=\frac{x-1}{2}\).
We can prove that this is correct by showing for all real numbers that \((g\circ f)(x) = x\) and vice versa as required.

As an example, consider \(f_0\colon \mathbb N \to \mathbb N\) given by \(f_0(x)=x+1\), and \(f_1\colon \mathbb N \to \mathbb N\) given by \(f_1(x) = x-1\) if \(x\neq 1\) and 1 if \(x=1\).
\(f_1\circ f_0 = 1_{\mathbb N}\) but \(f_0\circ f_1 \neq 1_{\mathbb N}\) because they disagree at 1.
So we must check inverses both ways.

In fact, \(f\colon A \to B\) is invertible if and only if it is a bijection.
\begin{itemize}
	\item (forward implication) Let \(g\) be the inverse of \(f\).
	      It is surjective because \(\forall b \in B\), we have \(b=f(g(b))\).
	      It is injective because given two elements \(a,a'\) such that \(f(a) = f(a')\), we have \(g(f(a)) = g(f(a')) = a = a'\) as required.
	      So it is bijective.
	\item (backward implication) Suppose \(f\) is bijective.
	      Let \(g(b)\) be the unique point \(a \in A\) with \(f(a) = b\) for all \(b \in B\).
	      Then this \(g\) is the inverse of \(f\).
\end{itemize}

\subsection{Relations}
A relation on a set \(X\) is a subset of \(R \subseteq X \times X\).
We usually write \(aRb\) to denote \((a, b) \in R\).
Here are some examples.
\begin{enumerate}
	\item On \(\mathbb N\), \(aRb\) if \(a \equiv b\ (5)\).
	      For example, \(2R12\) but not \(2R11\).
	\item On \(\mathbb N\), \(aRb\) if \(a \mid b\).
	\item On \(\mathbb N\), \(aRb\) if \(a \neq b\).
	\item On \(\mathbb N\), \(aRb\) if \(a=b \pm 1\).
	\item On \(\mathbb N\), \(aRb\) if \(\abs{a-b} \leq 2\).
	\item On \(\mathbb N\), \(aRb\) if either \(a, b \leq 6\) or \(a, b > 6\).
\end{enumerate}
A relation may have a number of important properties:
\begin{itemize}
	\item (reflexive) If \(\forall x \in X\), \(xRx\), e.g.
	      examples 1, 2, 5, 6.
	\item (symmetric) If \(\forall x, y \in X\), \(xRy \implies yRx\), e.g.
	      examples 1, 3, 4, 5, 6.
	\item (transitive) If \(\forall x, y, z \in X\), \(xRy, yRz \implies xRz\), e.g.
	      examples 1, 2, 6.
\end{itemize}
An equivalence relation is a relation that is reflexive, symmetric and transitive.
Examples 1, 6 above are equivalence relations.
Here are some more examples.
\begin{enumerate}
	\item On \(\mathbb N\), \(xRy\) if \(x=y\).
	\item Considering a partition of set \(X\) into subsets \(C_1, C_2, \dots, i \in I\) where the \(C_i\) are non-empty and disjoint, and their union is \(X\).
	      Then consider the relation \(aRb\) if \(\exists i\) such that \(a \in C_i\) and \(b \in C_i\).
	      \(aRb\) is an equivalence relation.
	      In fact, all equivalence relations can be considered to be in this form; we will prove this shortly.
\end{enumerate}
For an equivalence relation \(R\) on a set \(X\), and \(x \in X\), we define the equivalence class \([x] = \{ y \in X: y R x \}\).
In the first example 1 above, \([2] = \{ y \in \mathbb N : y \equiv 2\ (5) \}\).

\subsection{Equivalence classes as partitions}
\begin{proposition}
	Let \(R\) be an equivalence relation on a set \(X\).
	Then the equivalence classes of \(R\) partition \(X\).
\end{proposition}
\begin{proof}
	Each equivalence class \([x]\) is non-empty, since \(x = x\).
	Further,
	\[
		\bigcup_{x \in X} = X
	\]
	since \(x \in [x]\) for all \(x \in X\).
	Now we must show that the classes are disjoint, or are equal.
	Given \(x, y\) with \([x] \cap [y] \neq \varnothing\), we need to show that \([x] = [y]\).
	Choose some \(z\) such that \(z \in [x] \cap [y]\).
	Then, \(zRx\) and \(zRy\), so \(xRy\).
	Thus for any \(t\), \(tRx \implies tRy\) due to transitivity, and \(tRy \implies tRx\) for the same reason.
	So \([x] = [y]\).
\end{proof}
As an example, does there exist an equivalence relation on \(\mathbb N\) with three equivalence classes, two of which are infinite, and one of which is finite?
Yes---we can break up \(\mathbb N\) into three parts, for example positive numbers, negative numbers and zero.
This defines an equivalence relation.

\subsection{Quotients}
Given an equivalence relation \(R\) on a set \(X\), the quotient of \(X\) by \(R\) is
\[
	X/R = \{ [x]: x \in X \}
\]
The map \(q\colon X\to X/R\) given by \(x \mapsto [x]\) is called the `quotient map' or `projection map'.
As an example, on \(\mathbb Z \times \mathbb N\), let us define \((a, b)R(c, d)\) to be true if \(ad=bc\).
This is an equivalence relation that demonstrates equivalence of rational numbers, where \(a, c\) are the numerators and \(b, d\) are denominators.
Here, \(\mathbb Z \times \mathbb N / R\) is a copy of \(\mathbb Q\), associating \([(a, b)]\) with \(a/b\).
Then, \(q\colon \mathbb Z \times \mathbb N \to \mathbb Q\) would map \((a, b)\) to \(a/b\).
